using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0697. 数组的度")]
    public class No0697_FindShortestSubArray : AbsBaseTestItem
    {
        /*
        给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
        你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
        示例 1：
            输入：[1, 2, 2, 3, 1]
            输出：2
            解释：
                输入数组的度是2，因为元素1和2的出现频数最大，均为2.
                连续子数组里面拥有相同度的有如下所示:
                [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
                最短连续子数组[2, 2]的长度为2，所以返回2.
        示例 2：
            输入：[1,2,2,3,1,4,2]
            输出：6
            提示：
                nums.length 在1到 50,000 区间范围内。
                nums[i] 是一个在 0 到 49,999 范围内的整数。
        */

        public override void OnTest()
        {
            Assert.TestExe(FindShortestSubArray, new int[] { 1, 2, 2, 3, 1 }, 2);
            Assert.TestExe(FindShortestSubArray, new int[] { 1, 2, 2, 3, 1, 4, 2 }, 6);
        }

        public int FindShortestSubArray(int[] nums)
        {
            var dic = new Dictionary<int, int[]>();
            for (int i = 0; i < nums.Length; i++)
            {
                int value = nums[i];
                if (!dic.ContainsKey(value))
                {
                    dic[value] = new int[] { 1, i, i };
                }
                else
                {
                    dic[value][0]++;
                    dic[value][2] = i;
                }
            }
            int maxNum = 0, minLen = 0;
            foreach (int key in dic.Keys)
            {
                int[] arr = dic[key];
                int len = arr[2] - arr[1] + 1;
                if (maxNum < arr[0])
                {
                    maxNum = arr[0];
                    minLen = len;
                }
                else if (maxNum == arr[0])
                {
                    if (minLen > len)
                    {
                        minLen = len;
                    }
                }
            }
            return minLen;
        }
    }
}
